// https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

class Solution
{
public:
  vector<vector<int>> threeSum(vector<int> &nums)
  {
    int n = nums.size();
    vector<vector<int>> vec;

    // 先【排序】传入的 nums 序列
    sort(nums.begin(), nums.end());

    // 枚举 a
    for (int first = 0; first < n; ++first)
    {
      // 需要和上一次枚举的 a 不相同
      if (first > 0 && nums[first] == nums[first - 1])
        continue;

      // c = 数组【最右端】
      int third = n - 1;

      // target = -a
      int target = -nums[first];

      // 枚举 b + c == target
      for (int second = first + 1; second < n; ++second)
      {
        // 需要和上一次枚举的 b 不相同
        if (second > first + 1 && nums[second] == nums[second - 1])
          continue;

        // 需要保证 b 在 c 左侧，并且如果 b + c > target 则 c【往前】走
        while (second < third && nums[second] + nums[third] > target)
          --third;

        // 随着 b 不断往后移动，如果 b 相遇 c 则肯定【不存在】a+b+c=0
        // 可以退出循环
        if (second == third)
          break;

        // 出现 b + c == target
        if (nums[second] + nums[third] == target)
          vec.push_back({
            nums[first], // 记录 a
            nums[second], // 记录 b
            nums[third] // 记录 c
          });
      }
    }

    return vec;
  }
};
